/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    /*    这种做法表示路径一定会经过根部 但事实上路径不一定会经过根部，也许最大路径就在某个子树，
    int maxvalue=INT_MIN;
    int maxPathSum(TreeNode* root) {
        // write code here
        if(!root) return 0;
        
       int leftmax=max(0,bfs(root->left));
       int rightmax=max(0,bfs(root->right));
        return  root->val+leftmax+rightmax;
        
    }
    int bfs(TreeNode * root)
    {
       if(!root) return 0;
        int leftMax=max(0,bfs(root->left));
        int rightMax=max(0,bfs(root->right));
        return max(leftMax,rightMax)+root->val;
    }
    */
    
        int maxvalue=INT_MIN;
    int maxPathSum(TreeNode* root) {
        // write code here
        if(!root) return 0;
        
        bfs(root);
        return  maxvalue;
        
    }
    int bfs(TreeNode * root)
    {
       if(!root) return 0;
        int leftMax=max(0,bfs(root->left));
        int rightMax=max(0,bfs(root->right));
        maxvalue=max(maxvalue,leftMax+rightMax+root->val);
        return max(leftMax,rightMax)+root->val;
    }
};